Tước hiệu Khả hãn được ghi nhận lần đầu tiên vào khoảng giữa những năm 283 đến 289, khi thủ lĩnh bộ tộc Tiên Ti là Mộ Dung Thổ Cốc Hồn (Murong Tuyuhun) trong nỗ lực tìm cách thoát khỏi quyền kiểm soát của em trai mình là Mộ Dung Hối, đã dẫn theo các thuộc hạ của mình từ Liêu Đông đến vùng sa mạc Ordos để lập quốc gia riêng, lấy tên là Thổ Cốc Hồn (Tuyuhun). Theo lời thuộc hạ, ông đã lấy tước hiệu là Khả hãn để thể hiện sự khác biệt với em mình đang cai quản vương quốc Tiền Yên ở phía đông.[3]

Người Nhu Nhiên được cho là người đầu tiên sử dụng tước hiệu Khả hãn lẫn Hãn, thay cho tước hiệu Thiền vu của người Hung Nô, được cho là ảnh hưởng bởi tiếng Turk.[4] Tuy nhiên, một số học giả lại cho rằng người Nhu Nhiên chính là một trong những bộ tộc Mông Cổ trước thời Thành Cát Tư Hãn.[5][6][7]